package top.ivansong92.example.leetcode.learning.data.struct.array;


import org.junit.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class TestExample3 {


    @Test
    public void testLemonadeChange() {
        System.out.println(lemonadeChange(new int[]{5,5,10}));
        System.out.println(lemonadeChange(new int[]{5,10,5,20}));
    }

    /**
     * 860. 柠檬水找零
     * @param bills
     * @return
     */
    public boolean lemonadeChange(int[] bills) {
        if (bills == null || bills.length == 0) {
            return true;
        }

        int fivePlus = 0, tenPlus = 0;
        for (int bill : bills) {
            switch (bill) {
                case 5:
                    fivePlus ++;
                    break;
                case 10:
                    fivePlus --;
                    tenPlus ++;
                    break;
                case 20:
                    int plus = bill - 5;
                    if (tenPlus > 0) {
                        tenPlus --;
                        plus -= 10;
                    }
                    fivePlus -= plus / 5;
                    break;
                default:
                    return false;
            }

            if (fivePlus < 0) {
                return false;
            }
        }
        return true;
    }


    /**
     * 1160. 拼写单词
     * @param words
     * @param chars
     * @return
     */
    public int countCharacters(String[] words, String chars) {
        int res = 0;
        if (words == null || words.length == 0 || chars == null || chars.length() == 0) {
            return res;
        }

        Map<Character, Integer> charCountMap = stringToCharCounterMap(chars);
        if (charCountMap.size() == 0) {
            return res;
        }

        Map<Character, Integer> wordChCounterMap = null;
        for (String word : words) {
            if (word == null || word.length() == 0) {
                continue;
            }
            wordChCounterMap = stringToCharCounterMap(word);
            boolean match = true;
            for(Map.Entry<Character, Integer> entry : wordChCounterMap.entrySet()) {
                Integer charCounter = charCountMap.get(entry.getKey());
                if (charCounter == null) {
                    match = false;
                    break;
                }
                if (charCounter.compareTo(entry.getValue()) < 0) {
                    match = false;
                    break;
                }
            }
            if (match) {
                res += word.length();
            }
        }

        return res;
    }

    private Map<Character, Integer> stringToCharCounterMap(String string) {
        Map<Character, Integer> charCountMap = new HashMap<>();
        for(char ch : string.toCharArray()) {
            Integer val = charCountMap.get(ch);
            if (val == null) {
                val = 0;
            }
            val ++;
            charCountMap.put(ch, val);
        }
        return charCountMap;
    }

    /**
     * 406. 根据身高重建队列
     * @param people
     * @return
     */
    public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length == 0) {
            return people;
        }

        int[][] firstSort = new int[people.length][2];
        firstSort[0]= people[0];

        for(int i = 1; i < people.length; i ++) {
            int[] val = people[i];
            int index = i - 1;
            while (index >= 0 && (firstSort[index][0] < val[0] || (firstSort[index][0] == val[0] && firstSort[index][1] > val[1]))) {
                firstSort[index + 1] = firstSort[index];
                index--;
            }
            firstSort[index + 1] = val;
        }

        int[][] res = new int[firstSort.length][2];
        res[0] = firstSort[0];
        for(int i = 1; i < res.length; i ++) {
            int[] val = firstSort[i];
            if (val[1] >= i) {
                res[i] = val;
            } else {
                doInsertMove(res, val[1], i, val);
            }
        }

        return res;
    }

    private void doInsertMove(int[][] res, int start, int end, int[] val) {
        for(int i = end; i > start; i --) {
            res[i] = res[i - 1];
        }
        res[start] = val;
    }


    @Test
    public void testInsert() {
        System.out.println(Arrays.toString(reconstructQueue(new int[][]{{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}})));
    }


    @Test
    public void testfindCircleNum() {
        System.out.println(findCircleNum(new int[][]{
                {1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
                {0,1,0,1,0,0,0,0,0,0,0,0,0,1,0},
                {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,1,0,1,0,0,0,1,0,0,0,1,0,0,0},
                {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
                {0,0,0,1,0,0,0,1,1,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,1,1,0,0,0,0,0,0},
                {1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
                {0,0,0,1,0,0,0,0,0,0,0,1,0,0,0},
                {0,0,0,0,1,0,0,0,0,0,0,0,1,0,0},
                {0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}}));
    }

    /**
     * 547. 省份数量
     * @param isConnected
     * @return
     */

    public int findCircleNum(int[][] isConnected) {
        if (isConnected == null || isConnected.length == 0) {
            return 0;
        }

        Map<String, String> connectMap = new HashMap<>();
        for(int i = 0; i < isConnected.length; i ++) {
            connectMap.put("#" + i + "#", "#");
        }
        int[] array = null;
        for(int i = 0; i < isConnected.length; i ++) {
            array = isConnected[i];
            for(int j = i + 1; j < array.length; j ++) {
                int val = array[j];
                if (val == 0) {
                    continue;
                }
                connectMap.remove("#" + i + "#");
                connectMap.remove("#" + j + "#");
                boolean put = false;
                for(String key : connectMap.keySet().stream().collect(Collectors.toList())) {
                    if (key.contains("#" + i + "#")) {
                        connectMap.remove(key);
                        if (put) {
                            for (String key1 : connectMap.keySet().stream().collect(Collectors.toList())) {
                                if (key1.contains("#" + i + "#") || key1.contains("#" + j + "#")) {
                                    connectMap.remove(key1);
                                    connectMap.put(key + key1, "#");
                                    break;
                                }
                            }
                        } else {
                            connectMap.put(key + "#" + j + "#", "#");
                            put = true;
                            continue;
                        }
                    }

                    if (key.contains("#" + j + "#")) {
                        connectMap.remove(key);
                        if (put) {
                            for (String key1 : new ArrayList<>(connectMap.keySet())) {
                                if (key1.contains("#" + i + "#") || key1.contains("#" + j + "#")) {
                                    connectMap.remove(key1);
                                    connectMap.put(key + key1, "#");
                                    break;
                                }
                            }
                        } else {
                            connectMap.put(key + "#" + i + "#", "#");
                            put = true;
                        }
                    }
                }
                if (!put) {
                    connectMap.put("#" + i + "#" + j + "#", "#");
                }

                if (connectMap.size() == 1) {
                    return 1;
                }
            }
        }

        return connectMap.size();
    }

    /**
     * 628. 三个数的最大乘积
     * @param nums
     * @return
     */
    public int maximumProduct(int[] nums) {
        if (nums.length == 3) {
            return nums[0] * nums[1] * nums[2];
        }

        Arrays.sort(nums);
        return Math.max(nums[0] * nums[1] * nums[nums.length - 1], nums[nums.length - 3] * nums[nums.length - 2] * nums[nums.length - 1]);
    }

    /**
     *  剑指 Offer 42. 连续子数组的最大和
      * @param nums
     *  @return
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length < 1) {
            return Integer.MIN_VALUE;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        int[] tmp = new int[len];
        tmp[0] = nums[0];
        int max = nums[0];

        for (int i = 1; i < len; i++) {
            int val = nums[i];
            tmp[i] = Math.max(val, val + tmp[i - 1]);
            max = Math.max(max, tmp[i]);
        }
        return max;
    }


    /**
     * 剑指 Offer 29. 顺时针打印矩阵
     * @param matrix
     * @return
     */
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        int[] res = new int[matrix.length * (matrix[0].length)];
        int index = 0;

        int x_min = 0, y_min = 0, x_max = matrix[0].length - 1, y_max = matrix.length - 1;
        while (true) {
            //先向右
            for (int i = x_min; i <= x_max; i++) {
                res[index] = matrix[y_min][i];
                index++;
            }
            y_min ++;

            if (y_max < y_min) {
                break;
            }

            //向下
            for(int j = y_min; j <= y_max; j ++) {
                res[index] = matrix[j][x_max];
                index++;
            }
            x_max --;

            if (x_max < x_min) {
                break;
            }

            //向左
            for (int i = x_max; i >= x_min; i --) {
                res[index] = matrix[y_max][i];
                index++;
            }

            y_max --;

            // 向上
            for(int j = y_max; j >= y_min; j --) {
                res[index] = matrix[j][x_min];
                index++;
            }
            x_min ++;

        }

        return res;
    }

    @Test
    public void testMinSubArrayLen() {
        System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3}));
    }


    /**
     * 209. 长度最小的子数组
     * https://leetcode.cn/problems/minimum-size-subarray-sum/
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;

        if (len == 1) {
            return nums[0] >= target ? 1 : 0;
        }

        int left = 0, right = 0, minLen = 0, sub = 0;
        while (left < len && right < len) {
            if (left == right) {
                int val = nums[left];
                if (val >= target) {
                    return 1;
                }
                right++;
                sub = val;
                continue;
            }
            int rightVal = nums[right];
            if (sub + rightVal >= target) {
                int subLen = right - left + 1;
                minLen = minLen == 0 ? subLen : Math.min(minLen, subLen);
                sub -= nums[left];
                left++;
            } else {
                sub += rightVal;
                right++;
            }
        }

        return minLen;
    }

    @Test
    public void testfindAnagrams() {
        System.out.println(findAnagrams("cbaebabacd", "abc"));
    }

    /**
     * 438. 找到字符串中所有字母异位词
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        if (s == null || s.length() == 0 || p == null || p.length() == 0 || p.length() > s.length()) {
            return Collections.emptyList();
        }

        int[] pArray = new int[26];
        for(char ch : p.toCharArray()) {
            pArray[ch - 'a'] += 1;
        }
        List<Integer> res = new ArrayList<>();
        char[] sArray = s.toCharArray();
        int[] tmp = null;
        boolean match = true;
        for(int i = 0; i <= sArray.length - p.length(); i ++) {
            char ch = sArray[i];
            int val = pArray[ch - 'a'];
            if (val == 0) {
                continue;
            }
            tmp = new int[26];
            match = true;
            sub: for(char subCh : s.substring(i, i + p.length()).toCharArray()) {
                val = pArray[subCh - 'a'];
                if (val == 0) {
                    match = false;
                    break sub;
                }

                if (tmp[subCh - 'a'] == 0) {
                    tmp[subCh - 'a'] = val + 1;
                } else if (tmp[subCh - 'a'] == 1) {
                    match = false;
                    break sub;
                }
                tmp[subCh - 'a'] -= 1;
            }
            if (match) {
                res.add(i);
            }
        }
        return res;
    }

    /**
     * 349. 两个数组的交集
     * @param nums1
     * @param nums2
     * @return
     */

    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> filter = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
        return Arrays.stream(nums2).filter(e-> filter.contains(e)).distinct().toArray();
    }


    /**
     * 447. 回旋镖的数量
     * @param points
     * @return
     */

    public int numberOfBoomerangs(int[][] points) {//148
        if (points == null || points.length < 3) {
            return 0;
        }

        int res = 0;
        Map<Integer, Integer> distanceMap;
        int len = points.length;

        for (int i = 0; i < len; i++) {
            int[] point = points[i];
            distanceMap = new HashMap<>();
            for (int j = 0; j < len; j++) {
                if (i == j) {
                    continue;
                }
                int distance = calPointDistance(point, points[j]);
                Integer count = distanceMap.get(distance);
                if (count == null) {
                    count = 0;
                }
                count++;
                distanceMap.put(distance, count);
            }

            for (Map.Entry<Integer, Integer> entry : distanceMap.entrySet()) {
                res += entry.getValue() * (entry.getValue() - 1);
            }
        }
        return res;
    }

    public int numberOfBoomerangsV2(int[][] points) {//92
        if (points == null || points.length < 3) {
            return 0;
        }

        int res = 0;

        Map<Integer, AtomicInteger> distanceMap = new HashMap<>(1024);//优化点1：提前分配map空间

        int len = points.length;

        for (int i = 0; i < len; i++) {
            int[] point = points[i];
            for (int j = 0; j < len; j++) {
                if (i != j) {
                    continue;
                }
                int distance = calPointDistance(point, points[j]);
                AtomicInteger count = distanceMap.computeIfAbsent(distance, k -> new AtomicInteger(0));//优化点2：减少map的put操作
                count.incrementAndGet();
            }

            for (Map.Entry<Integer, AtomicInteger> entry : distanceMap.entrySet()) {
                int val = entry.getValue().get();
                if (val > 1) {//优化点3：取值一次并减少运算
                    res += val * (val - 1);
                }
            }
            distanceMap.clear();
        }
        return res;
    }


    private int calPointDistance(int[] point1, int[] point2) {
        int x = point1[0] - point2[0];
        int y = point1[1] - point2[1];
        return x * x + y * y;
    }


    /**
     * 149. 直线上最多的点数
     * @param points
     * @return
     */

    public int maxPoints(int[][] points) {
        if (points == null || points.length <= 1) {
            return 0;
        }

        int len = points.length;
        if (len == 2) {
            return len;
        }

        int res = 0;

        Map<Gradient, AtomicInteger> distanceMap = new HashMap<>(1024);

        for (int i = 0; i < len; i++) {
            int[] point = points[i];
            for (int j = i + 1; j < len; j++) {
                int[] point1 = points[j];
                AtomicInteger count = distanceMap.computeIfAbsent(new Gradient(point1[0] - point[0], point1[1] - point[1]), k -> new AtomicInteger(1));
                count.incrementAndGet();
            }

            for (Map.Entry<Gradient, AtomicInteger> entry : distanceMap.entrySet()) {
                int val = entry.getValue().get();
                res = Math.max(res, val);
            }
            distanceMap.clear();
        }
        return res;
    }

    private static class Gradient {
        int xDis, yDis;

        public Gradient(int xDis, int yDis) {
            this.xDis = xDis;
            this.yDis = yDis;
        }

        @Override
        public int hashCode() {
            if (xDis == 0) {
                return 0;
            }
            return (int)(((double) yDis / (double) xDis) * 1000000);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }

            if (obj instanceof Gradient) {
                Gradient aim = (Gradient) obj;
                return aim.yDis * this.xDis == aim.xDis * this.yDis;
            }
            return false;
        }
    }

    public int maxPointsV2(int[][] points) {
        if (points == null || points.length <= 1) {
            return 0;
        }

        int len = points.length;
        if (len == 2) {
            return len;
        }

        int res = 0;

        for (int i = 0; i < len; i++) {
            int[] point = points[i];
            int x = point[0], y = point[1];
            for (int j = i + 1; j < len; j++) {
                int[] point1 = points[j];
                int x1 = point1[0], y1 = point1[1];
                int count = 2;
                for (int k = j + 1; k < len; k++) {
                    int x2 = points[k][0], y2 = points[k][1];
                    if ((x-x1) * (y-y2) == (x-x2) * (y-y1)) {
                        count ++;
                    }
                }
                res = Math.max(res, count);
            }
        }
        return res;
    }


    @Test
    public void testContainsNearbyDuplicate() {
        System.out.println(containsNearbyDuplicate(new int[]{1,2,3,1,2,3}, 2));
    }

    /**
     * 219. 存在重复元素 II
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return false;
        }

        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            Integer index = numMap.get(val);
            if (index == null) {
                numMap.put(val, i);
                continue;
            }

            if (i - index <= k) {
                return true;
            }

            numMap.put(val, i);
        }

        return false;
    }


    public boolean containsNearbyDuplicateV2(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return false;
        }

        TreeSet<Integer> filter = new TreeSet<>();
        for (int i = 0; i < nums.length && i <= k; i++) {
            int val = nums[i];
            if (!filter.add(val)) {
                return true;
            }
        }

        for (int i = k + 1; i < nums.length; i++) {
            filter.remove(nums[i - k - 1]);
            int val = nums[i];
            if (!filter.add(val)) {
                return true;
            }
        }

        return false;
    }

    @Test
    public void testContainsNearbyAlmostDuplicateV2() {
        System.out.println(containsNearbyAlmostDuplicateV2(new int[]{1,2,3,1}, 3, 0));
    }

    /**
     * 220. 存在重复元素 III
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length <= 1 || k <= 0) {
            return false;
        }

        for (int i = 0; i < nums.length - 1; i++) {
            int val = nums[i];
            for (int j = i + 1; j < nums.length && j <= i + k; j++) {
                long plus = Math.abs((long)nums[j] - (long)val);
                if (plus <= t) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean containsNearbyAlmostDuplicateV2(int[] nums, int k, int t) {
        if (nums == null || nums.length <= 1 || k <= 0 || t < 0) {
            return false;
        }

        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (i > k) {
                set.remove((long) nums[i - k - 1]);
            }
            int val = nums[i];
            Long ceilVal = set.ceiling((long) val - (long) t);
            if (ceilVal != null && ceilVal <= (long) val + (long) t) {
                return true;
            }

            set.add((long)val);
        }
        return false;
    }


    @Test
    public void testLengthOfLIS() {
        System.out.println(lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}));
    }

    /**
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }

        Set<Integer> res = new HashSet<>();

        for (int i = 0; i < len; i++) {
            doFind(res, nums[i] + "", i + 1, len, nums, nums[i]);
        }

        return res.stream().max(Comparator.comparing(Integer::intValue)).orElse(0);
    }

    private void doFind(Set<Integer>  list, String s, int start, int end, int[] nums, int max) {
        if (start >= end) {
            list.add(s.split(",").length);
            return;
        }

        for (int i = start; i <= end; i++) {
            if (i == end) {
                list.add(s.split(",").length);
                break;
            }
            if (nums[i] <= max) {
                continue;
            }
            doFind(list, s + "," + nums[i], i + 1, end, nums, nums[i]);
        }
    }

    /**
     * 1995. 统计特殊四元组
     *
     * @param nums
     * @return
     */
    public int countQuadruplets(int[] nums) {
        if (nums == null || nums.length < 4) {
            return 0;
        }

        int res = 0;
        for (int i = 3; i < nums.length; i++) {
            int val = nums[i];
            for (int j = 0; j < i; j++) {
                for (int k = j + 1; k < i; k++) {
                    for (int m = k + 1; m < i; m++) {
                        if (nums[j] + nums[k] + nums[m] == val) {
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }

    public boolean isUnique(String astr) {
        if (astr == null || astr.length() == 0) {
            return true;
        }
        Set<Character> filter = new HashSet<>();
        for(char ch : astr.toCharArray()) {
            if (filter.contains(ch)) {
                return false;
            }
            filter.add(ch);
        }
        return true;
    }


    @Test
    public void testLRU() {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        cache.put(3, 3);
        System.out.println(cache.get(3));

    }

    public String compressString(String S) {
        if (S == null || S.length() <= 1) {
            return S;
        }

        int len = S.length();
        int num = 1;
        StringBuilder res = new StringBuilder(S.charAt(0) + "");
        for(int i = 1; i < len; i ++) {
            char pre = S.charAt(i - 1);
            char cur = S.charAt(i);
            if (pre != cur) {
                res.append("" + num).append(cur);
                num = 1;
            } else {
                num ++;
            }
        }
        res.append(num);

        return res.length() >= len ? S : res.toString();
    }

    /**
     * 面试题 01.07. 旋转矩阵
     *情况一：顺时针转 90 度：先转置再左右镜像
     * 1 2 3               7 4 1
     * 4 5 6               8 5 2
     * 7 8 9               9 6 3
     * 情况二：顺时针转 180 度:先上下镜像，再左右镜像（先左右再上下也可）
     * 1 2 3               9 8 7
     * 4 5 6               6 5 4
     * 7 8 9               3 2 1
     * 情况三：顺时针转 270 度：先转置再上下镜像
     * 1 2 3              3 6 9
     * 4 5 6              2 5 8
     * 7 8 9              1 4 7
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        if (n <= 1) {
            return;
        }
        //转置
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < i; j ++) {
                int val = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = val;
            }
        }

        //左右调换
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < n/2; j ++) {
                int val = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n-1 - j] = val;
            }
        }
    }

    public void rotateV2(int[][] matrix) {
        int n = matrix.length;
        if (n <= 1) {
            return;
        }
        //转置
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < i; j ++) {
                int val = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = val;
            }
        }

        //左右调换
        int left = 0, right = n - 1;
        while (left < right) {
            for(int i = 0; i < n; i ++) {
                int val = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = val;
            }
            left ++;
            right --;
        }
    }

    @Test
    public void testsearch() {
        System.out.println(search(new int[]{1, 4, 4, 5, 5, 12, 17, 17, 20, 20, 21, 22, 22, 24, 24, 27, 29, 30, 32, 41, 41, 45, 45, 46, 47, 49, 53, 57, 57, 63, 63, -63, -63, -62, -56, -52, -48, -47, -44, -43, -43, -42, -41, -39, -39, -37, -34, -33, -32, -32, -29, -26, -25, -23, -16, -13, -11, -8, -7, -7, -6, -4, -2, -2}, -23));

    }
    /**
     * 面试题 10.03. 搜索旋转数组
     * @param arr
     * @param target
     * @return
     */
    public int search(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int len = arr.length;
        int startIndex = 0;
        for(int i = 1; i < len; i ++) {
            if (arr[i] < arr[i-1]) {
                startIndex = i;
                break;
            }
        }

        int res = doFind(arr, target, 0, startIndex - 1);
        if (res >= 0) {
            return res;
        }

        return doFind(arr, target, startIndex, len - 1);
    }

    private int doFind(int[] arr, int target, int from, int end) {
        int left = from;
        int right = end;
        while (left <= right) {
            int val = arr[left];
            if (target == val) {
                return left;
            } else if (target < val) {
                break;
            }

            val = arr[right];
            if (target == val) {
                if (arr[right-1] != val) {
                    return right;
                } else {
                    right --;
                    continue;
                }
            } else if (target > val) {
                break;
            }

            int mid = left + (right - left) / 2;
            val = arr[mid];
            if (target == val) {
                if (arr[mid - 1] != val) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else if (target > val) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 剑指 Offer 38. 字符串的排列
     * @param s
     * @return
     */
    public String[] permutation(String s) {
        if (s == null || s.length() == 0) {
            return new String[0];
        }
        int len = s.length();
        if (len == 1) {
            return new String[]{s};
        }
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        List<String> strings = new ArrayList<>();
        boolean[] visited = new boolean[len];
        doPermutation(chars, "", visited, strings);
        return strings.toArray(new String[0]);
    }

    private void doPermutation(char[] chars, String s, boolean[] visited, List<String> res) {
        if (s.length() == chars.length) {
            res.add(s);
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (i > 0 && chars[i] == chars[i - 1] && visited[i - 1]) {
                continue;
            }
            visited[i] = true;
            doPermutation(chars, s + chars[i], visited, res);
            visited[i] = false;
        }
    }

    public String[] permutationV2(String s) {
        if (s == null || s.length() == 0) {
            return new String[0];
        }
        int len = s.length();
        if (len == 1) {
            return new String[]{s};
        }
        char[] chars = s.toCharArray();
        List<String> strings = new ArrayList<>();
        boolean[] visited = new boolean[len];
        doPermutationV2(chars, "", visited, strings);
        return strings.toArray(new String[0]);
    }

    private void doPermutationV2(char[] chars, String s, boolean[] visited, List<String> res) {
        if (s.length() == chars.length) {
            res.add(s);
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            doPermutation(chars, s + chars[i], visited, res);
            visited[i] = false;
        }
    }

    /**
     *
     * 剑指 Offer 45. 把数组排成最小的数
     * @param nums
     * @return
     */
    public String minNumber(int[] nums) {
        if (nums == null || nums.length == 0){
            return "";
        }
        return Arrays.stream(nums)
                .mapToObj(String::valueOf)
                .sorted((e1, e2)-> (e1 + e2).compareTo(e2 + e1))
                .collect(Collectors.joining());
    }

    /**
     * 5. 最长回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        String res = s.substring(0, 1);
        int max = 1;
        for(int i = 0; i < s.length() - 1; i ++) {
            for(int j = s.length(); j >= i + max; j --) {
                String sub = s.substring(i, j);
                if (isPalindromeString(sub)) {
                    int val = j - i;
                    if (max < val) {
                        res = sub;
                        max = val;
                    }
                }
            }
        }
        return res;
    }

    private boolean isPalindromeString(String s) {
        if (s == null || s.length() <= 1) {
            return true;
        }
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }

    /**
     * 2006. 差的绝对值为 K 的数对数目
     * @param nums
     * @param k
     * @return
     */
    public int countKDifference(int[] nums, int k) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        int res = 0;
        for(int i = 0; i < nums.length - 1; i ++) {
            int val = nums[i];
            for(int j = i + 1; j < nums.length; j ++) {
                int plus = nums[j] - val;
                if (plus == k || plus == -k) {
                    res ++;
                }
            }
        }
        return res;
    }

    /**
     * 1447. 最简分数
     * @param n
     * @return
     */
    public List<String> simplifiedFractions(int n) {
        if (n <= 1) {
            return Collections.emptyList();
        }

        List<String> res = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (j > 1 && commonDivisor(i, j) != 1) {
                    continue;
                }
                res.add(j + "/" + i);
            }
        }
        return res;
    }
    private int commonDivisor(int big, int small) {
        int val = big % small;
        if (val == 0) {
            return small;
        }
        return commonDivisor(small, val);
    }

    @Test
    public void testlongestConsecutive() {
        System.out.println(longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1}));
    }
    /**
     * 128. 最长连续序列
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }
        Set<Integer> numSet = new HashSet<>();
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int n : nums) {
            min = Math.min(n, min);
            max = Math.max(n, max);
            numSet.add(n);
        }
        int res = 1;
        int lastIndex = min;
        boolean match = true;
        for(int i = min + 1; i <= max; i ++) {
            if (!numSet.contains(i)) {
                res = Math.max(res, i - lastIndex);
                lastIndex = i;
                match = false;
                continue;
            }
            if (match) {
                res = Math.max(res, i - lastIndex + 1);
            } else {
                lastIndex = i;
                match = true;
            }

        }
        return res;
    }

    public int longestConsecutiveV2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }
        Set<Integer> numSet = new HashSet<>();
        for (int n : nums) {
            numSet.add(n);
        }

        int res = 1;
        for (int n : nums) {
            int right = n;
            while (numSet.contains(right + 1)) {
                right++;
            }
            res = Math.max(res, right - n + 1);
        }
        return res;
    }

    public int longestConsecutiveV3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }
        Set<Integer> numSet = new HashSet<>();
        for (int n : nums) {
            numSet.add(n);
        }

        int res = 1;
        for (int n : nums) {
            if (!numSet.contains(n)) {
                continue;
            }
            numSet.remove(n);
            int right = n + 1;
            while (numSet.remove(right)) {
                right++;
            }

            int left = n - 1;
            while (numSet.remove(left)) {
                left --;
            }
            res = Math.max(res, right - left - 1);
        }
        return res;
    }

    /**
     * 56. 合并区间
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        Arrays.sort(intervals, Comparator.comparingInt(e -> e[0]));
        LinkedList<int[]> stack = new LinkedList<>();
        stack.addLast(intervals[0]);
        for(int i = 1; i < intervals.length; i ++) {
            int[] last = stack.removeLast();
            int[] cur = intervals[i];
            if (last[1] >= cur[0]) {
                int[] newArray = new int[2];
                newArray[0] = Math.min(last[0], cur[0]);
                newArray[1] = Math.max(last[1], cur[1]);
                stack.addLast(newArray);
            } else {
                stack.addLast(last);
                stack.addLast(cur);
            }
        }
        return stack.toArray(new int[0][]);
    }

    private boolean hasInter(int[] a1, int[] a2) {
        if (a1[0] >= a2[0] && a1[0] <= a2[1]) {
            return true;
        }
        return a2[0] >= a1[0] && a2[0] <= a1[1];
    }

    /**
     * 1984. 学生分数的最小差值
     * @param nums
     * @param k
     * @return
     */
    public int minimumDifference(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k == 1) {
            return 0;
        }
        Arrays.sort(nums);
        int len = nums.length;
        if (len <= k) {
            return nums[len - 1] - nums[0];
        }
        int res = nums[k - 1] - nums[0];
        for(int i = k; i < len; i ++) {
            res = Math.min(res, nums[i] - nums[i - k + 1]);
        }
        return res;
    }

    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() < 4 || s.length() > 12) {
            return Collections.emptyList();
        }
        List<String> res = new ArrayList<>();
        doSpliteIpString(s, new ArrayList<>(), res);
        return res;
    }
    private void doSpliteIpString(String s, List<String> subString, List<String> ipList) {
        if (s.length() == 0 || subString.size() == 4) {
            if (s.length() == 0 && subString.size() == 4) {
                ipList.add(String.join(".", subString));
            }
            return;
        }

        int first = s.charAt(0) - '0';
        if (first == 0) {
            subString.add(s.substring(0, 1));
            doSpliteIpString(s.substring(1), subString, ipList);
            subString.remove(subString.size() - 1);
        } else if (first >= 3) {
            for (int i = 1; i <= 2 && i <= s.length(); i++) {
                subString.add(s.substring(0, i));
                doSpliteIpString(s.substring(i), subString, ipList);
                subString.remove(subString.size() - 1);
            }
        } else {
            for (int i = 1; i <= 3 && i <= s.length(); i++) {
                String sub = s.substring(0, i);
                if (Integer.parseInt(sub) > 255) {
                    continue;
                }
                subString.add(sub);
                doSpliteIpString(s.substring(i), subString, ipList);
                subString.remove(subString.size() - 1);
            }
        }
    }

    /**
     * 1189. “气球” 的最大数量
     * @param text
     * @return
     */
    private final static int[] WORD_ARRAY = new int[26];
    private final static String WORD_STRING = "balloon";

    static {
        for (char ch : WORD_STRING.toCharArray()) {
            WORD_ARRAY[ch - 'a'] = WORD_ARRAY[ch - 'a'] + 1;
        }
    }

    public int maxNumberOfBalloons(String text) {
        if (text == null || text.length() < WORD_STRING.length()) {
            return 0;
        }
        int[] array = new int[26];
        for(char ch : text.toCharArray()) {
            int idx = ch - 'a';
            array[idx] = array[idx] + 1;
        }

        int res = Integer.MAX_VALUE;
        for(int i = 0; i < WORD_ARRAY.length; i ++) {
            int a = WORD_ARRAY[i];
            if (a == 0) {
                continue;
            }
            int b = array[i];
            res = Math.min(res, b / a);
        }
        return res;
    }
}

class LRUCache {
    private Map<Integer, Node> map;
    private Node tail;
    private Node head;
    private int capacity;
    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.val;
    }

    private void moveToHead(Node node) {
        if (node == head) {
            return;
        }
        if (node == tail) {
            tail = node.pre;
        }
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        if (next != null) {
            next.pre = pre;
        }
        node.pre = null;
        node.next = head;
        head.pre = node;
        head = node;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.val = value;
            moveToHead(node);
            return;
        }

        if (map.size() == capacity) {
            map.remove(tail.key);
            if (head != tail) {
                Node tmp = tail;
                tail = tail.pre;
                tail.next = null;
                tmp.pre = null;
            } else {
                head = null;
                tail = null;
            }
        }

        Node newNode = new Node(value, key, null, head);
        if (head != null) {
            head.pre = newNode;
        }

        if (tail == null) {
            tail = newNode;
        }

        head = newNode;
        map.put(key, newNode);
    }

    private static class Node {
        int val;
        int key;
        Node pre;
        Node next;

        public Node(int val, int key, Node pre, Node next) {
            this.val = val;
            this.key = key;
            this.pre = pre;
            this.next = next;
        }
    }
}
